/*
 * Copyright (c) 2022  by Junzhao
 * THIS FILE IS PART OF JAVA-Data-Structures-and-Algorithms PROJECT
 * All Rights Reserved.
 */

package 希尔;


/**
 * @Description 希尔排序
 * 希尔排序是希尔（Donald Shell）于1959年提出的一种排序算法。
 * 希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序。
 * <p>
 * 希尔排序法基本思想
 * 希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；
 * 随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止
 * 可以理解为对插入排序的先行处理
 * @Author 俊昭
 * @Date 2022/4/30
 */
public class Shell {
    /**
     * @description 交换式
     * @author 俊昭
     * @date 2022/5/1
     */
    public static int[] sortSwitch(int[] arr) {

        int len = arr.length;
        int half = len / 2;
        int temp;
        int gap = half;
        for (; 2 < gap; gap /= 2) {
            for (int i = gap; i < len; i++) {
                for (int j = i - gap; j >= 0; j -= gap) {
                    if (arr[j] > arr[j + gap]) {
                        temp = arr[j + gap];
                        arr[j + gap] = arr[j];
                        arr[j] = temp;
                    }
//                    }else{// 加上这两行也是12ms (这就是优化！)
//                        break;
//                    }
                }
            }
        }
        return arr;
    }


    /**
     * @description 移位式
     * @author 俊昭
     * @date 2022/5/1
     */
    public static int[] sortShift(int[] arr) {
        int len = arr.length;

        for (int gap = len / 2; 0 < gap; gap /= 2) {
            for (int i = gap; i < len; i++) {
                int index = i;
                int value = arr[i];

                while (index - gap >= 0 && arr[index - gap] > value) {
                    arr[index] = arr[index - gap];
                    index -= gap;
                }
                arr[index] = value;
//                if (arr[index] > arr[index - gap]) {
//                }
            }
        }
//        for (int i = 1; i < len; i++) {// 类比上面哦！
//            value = arr[i];
//            index = i - 1;
//            while (index >= 0 && arr[index] > value) {
//                arr[index + 1] = arr[index];
//                index--;
//            }
//            arr[index + 1] = value;
//        }
        return arr;
    }

}
 /* 交换式推演
        // 第一步
        for (int i = half; i < len; i++) {
            for (int j = i - half; j >= 0; j -= half) {//相当于一个直接插入排序
                if (arr[j] > arr[j + half]) {
                    int temp = arr[j + half];
                    arr[j + half] = arr[j];
                    arr[j] = temp;
                }
            }
        }
//        System.out.println(Arrays.toString(arr));
        // 第二步
        for (int i = quarter; i < len; i++) {
            for (int j = i - quarter; j >= 0; j -= quarter) {//相当于一个直接插入排序
                if (arr[j] > arr[j + quarter]) {
                    int temp = arr[j + quarter];
                    arr[j + quarter] = arr[j];
                    arr[j] = temp;
                }
            }
        }
//        System.out.println(Arrays.toString(arr));
        int value;
        int index;
        for (int i = 1; i < len; i++) {
            value = arr[i];
            index = i - 1;
            while (index >= 0 && arr[index] > value) {
                arr[index + 1] = arr[index];
                index--;
            }
            arr[index + 1] = value;
        }
*/